package leetcode100

// TODO 中序遍历 【-】 验证二叉搜索树
// TODO https://leetcode.cn/problems/validate-binary-search-tree/solution/si-chong-jie-ti-fang-fa-go-by-_robin-ok4m/

// 中序遍历, 使用了队列做记录
func isValidBST(root *TreeNode) bool {
	queue := []int{}   // 用于保存遍历结果, 并不算严格意义上的 队列
	midDfs2(root, &queue)

	// 验证大小顺序
	for i := 0; i < len(queue)-1; i++ {
		if queue[i] >= queue[i+1] {
			return false
		}
	}
	return true
}

// 中序遍历
func midDfs2(root *TreeNode, queue *[]int) {
	if root == nil {
		return
	}
	midDfs2(root.Left, queue)
	*queue = append(*queue, root.Val)
	midDfs2(root.Right, queue)
}
